// https://leetcode.cn/problems/cut-off-trees-for-golf-event/

// 题干：你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
//      0 表示障碍，无法触碰
//      1 表示地面，可以行走
//      比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
//      每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
//      你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
//      你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
//      可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树

// 示例：输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
//      输出：6

// 碎语：怎么转化成最短路径出口问题，BFS

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int m, n;
    typedef pair<int, int> PII;
public:
    int cutOffTree(vector<vector<int>>& forest)
    {
        m = forest.size(), n = forest[0].size();
        vector<PII> trees;
        for (int i = 0 ; i < m ; i++)
            for (int j = 0 ; j < n ; j++)
                if (forest[i][j] > 1) trees.push_back({i, j});

        sort (trees.begin(), trees.end(), [&](const PII& p1, const PII& p2)
        {
            return forest[p1.first][p1.second] < forest[p2.first][p2.second];
        });

        int ret = 0, bx = 0, by = 0;
        for (int i = 0 ; i < trees.size() ; i++){
            auto [a, b] = trees[i];
            int step = bfs(forest, bx, by, a, b);

            if (step == -1) return -1;
            ret += step;
            bx = a, by = b;
        }

        return ret;
    }

    bool vis[51][51];
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};

    int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey)
    {
        if (bx == ex && by == ey) return 0;

        memset(vis, 0, sizeof(vis));
        queue<PII> q;
        q.push({bx, by});
        vis[bx][by] = true;

        int step = 0;
        while (q.size()){
            step++;
            int sz = q.size();

            while (sz--){
                auto [a, b] = q.front();
                q.pop();

                for (int k = 0 ; k < 4 ; k++){
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && forest[x][y]){
                        if (x == ex && y == ey) return step;
                        vis[x][y] = true;
                        q.push({x, y});
                    }
                }
            }
        }

        return -1;
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> forest = {{1, 2, 3}, {0, 0, 4}, {7, 6, 5}};

    cout << sol.cutOffTree(forest) << endl;

    return 0;
}